package main.leetcode.offer.firstround.from51to68;

import java.util.Arrays;

/**
 * 66.构建乘积数组
 *
 * <p>给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素
 * B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
 *
 * <p>
 *
 * <p>示例:输入: [1,2,3,4,5] 输出: [120,60,40,30,24]
 *
 * <p>提示：所有元素乘积之和不会溢出 32 位整数 a.length <= 100000
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex66 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new ex66().constructArr(new int[] {1, 2, 3, 4, 5})));
    }

    // 从左到右的乘积，再从右到左，以val为右边乘过来的中间变量
    public int[] constructArr(int[] a) {
        //        int n = a.length;
        //        int[] left = new int[n];
        //        left[0] = 1;
        //        int[] res = new int[n];
        //        for (int i = 1; i < n; ++i) {
        //            left[i] = left[i - 1] * a[i - 1];
        //        }
        //        int tmp = 1;
        //        for (int i = n - 1; i >= 0; --i) {
        //            res[i] = tmp * left[i];
        //            tmp *= a[i];
        //        }
        //        return res;
        int n = a.length;
        int[] res = new int[n];
        for (int i = 0, val = 1; i < n; val *= a[i], ++i) {
            res[i] = val;
        }
        for (int i = n - 1, val = 1; i >= 0; val *= a[i], --i) {
            res[i] *= val;
        }
        return res;
    }
}
